package com.lw.leetcode.sort.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 1792. 最大平均通过率
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/27 21:53
 */
public class MaxAverageRatio {

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        PriorityQueue<double[]> queue = new PriorityQueue<>((o1, o2) -> {
            double x = ((o2[0] + 1) / (o2[1] + 1) - o2[0] / o2[1]);
            double y = ((o1[0] + 1) / (o1[1] + 1) - o1[0] / o1[1]);
            return Double.compare(x, y);
        });
        for (int[] c : classes) {
            queue.offer(new double[]{c[0], c[1]});
        }
        while (extraStudents > 0) {
            double[] maxClass = queue.poll();
            maxClass[0] += 1;
            maxClass[1] += 1;
            queue.offer(maxClass);
            extraStudents--;
        }
        double res = 0;
        while (!queue.isEmpty()) {
            double[] c = queue.poll();
            res += (c[0] / c[1]);
        }
        return res / n;
    }

}
